1. Field of the Invention
This invention generally relates to data processing, and more specifically, to communications in transactional environments.
2. Background Art
To improve performance, some computer systems may execute multiple threads concurrently. Generally, before a thread accesses a shared resource, it may acquire a lock of the shared resource. In situations where the shared resource is a data structure stored in memory, all threads that are attempting to access the same resource may serialize the execution of their operations in light of mutual exclusivity provided by the locking mechanism. This can be detrimental to system performance and may cause program failures, e.g., due to deadlock bugs.
To reduce or eliminate these adverse affects on performance resulting from utilization of locking mechanisms, some computer systems may use transactional memory. Transactional memory generally refers to a synchronization model that allows multiple threads to concurrently access a shared resource (such as a data structure stored in memory) without acquiring a lock as long as the accesses are non-conflicting, for example, as long as the accesses are directed to different portions of the shared resource.
Transactional memory is a paradigm that allows the programmer to design code as if multiple locations can be accessed and/or modified in a single atomic step. As typically defined, a transactional memory interface allows a programmer to designate certain sequences of operations as “atomic blocks” and “transactions,” which are guaranteed by the transactional memory implementation to either take effect atomically and in their entirety (in which case they are said to succeed), or have no externally visible effect (in which case they are said to fail). Thus, with transactional memory, it may be possible in many cases to complete multiple operations with no possibility of another thread observing partial results, even without holding any locks. The transactional memory paradigm can significantly simplify the design of concurrent programs.
Various Transactional Memory systems have been proposed and built to provide a simpler programming model for constructing multithreaded applications that need to control access to shared data structures. These systems allow software running on one thread of execution to optimistically assume that shared data structures can be updated without conflict with the accesses and updates of other threads of execution. The speculative updates to memory are kept pending until the transactional memory system confirms that no conflicts with storage accesses of other threads have occurred.
Transactional memory is widely considered to be the most promising avenue for addressing issues facing concurrent programming and execution. Using transactional memory, programmers may specify what should be done atomically, rather than how this atomicity should be achieved. The transactional memory implementation may then be responsible for guaranteeing the atomicity, largely relieving programmers of the complexity, tradeoffs, and software engineering problems associated with traditional lock-based programming approaches.
Transactional Memory promises significant simplifications to multithreaded programming, as compared to the more traditional approach of lock-based synchronization. In systems employing lock-based synchronization, programmers must specify how to achieve such atomicity, e.g., by associating each critical section with a mutual exclusion lock, establishing conventions for which locks must be acquired by which critical sections in order to ensure correctness, and specifying in what order the locks should be acquired in order to avoid deadlock.
Transactional memory may be implemented in hardware, in software, or in a combination of the two, in various embodiments. Hardware transactional memory (HTM) designs may be characterized as unbounded, bounded, or best effort implementations. For example, a bounded HTM may have a fixed-size, fully associative transactional cache, and a transaction may be committed if and only if it fits in that cache. Alternative best effort designs may piggyback on existing caches and other hardware structures such as store buffers, and therefore may be able to commit one large transaction while being unable to commit another significantly smaller one, depending on how the transactions happen to map to the existing structures.
If used directly, both bounded and best effort HTM designs may impose constraints on programmers because programmers may need to take into account the number or distribution of cache lines accessed by a transaction. Furthermore, the details of such constraints may vary from one machine to another, so programs that must respect those constraints may not be portable.
Software transactional memory (STM) implementations, in which the transactional memory is implemented entirely in software without special hardware support, may provide software engineering benefits similar to those provided by HTM. In STM implementations, coordination between conflicting concurrent transactions is mediated using software. Therefore, STM implementations may be built and used in existing systems without hardware modification. Because STM may be independent of hardware structures such as caches and store buffers, STM implementations may not be subject to the limitations of bounded and best effort HTMs described above. However, STM implementations are typically one to two orders of magnitude slower than HTM implementations, and a substantial performance gap between HTM and STM is likely to remain.
Hybrid Transactional Memory (HyTM) was designed to take advantage of the flexibility and generality of STM, but also to exploit HTM support (if it is available and when it is effective) to boost performance. A HyTM implementation minimally comprises a fully functional STM implementation, because it must work even if there is no HTM support available. Thus, using a HyTM implementation, any transaction may be executed in a software transactional memory mode without special hardware support (e.g., using only instructions that are standard in existing systems). The use of HyTM may allow programmers to develop, test, and execute programs that include transactions using existing systems (i.e., without hardware modification).
Transactional Memory offers many significant advantages. There are, however, limitations and challenges associated with the use of Transactional Memory. The basic idea of Transactional Memory is to be able to transparently undo all operations within a transaction so that no side effects are visible. Input/Output operations such as file writes, are one of the challenges, especially for Transactional Memory, as they do have side effects which cannot be undone. Consequently, Input/Output operations are either not permitted and result in an abort of the transaction or their usage is very restricted, limiting scalability and performance of the system.